#include <stdio.h>
#include <stdlib.h>

#include "edge_list.h"
#include "edge.h"
#include "point_list.h"
#include "point.h"
#include "triangle.h"
#include "triangle_list.h"

#include "linker.h"

double getPointX(Point * p){
    return p->x;
}

double getPointY(Point *p){
    return p->y;
}

PointList * getPointsFromEdges(EdgeList * list){
    PointList * points = newPointList(list->length);
    Edge * edges = list->edges;
    while(edges != NULL){
        if(!containsPoint(points,edges->a))
            addPoint(points,edges->a);
        if(!containsPoint(points,edges->b))
            addPoint(points,edges->b);
        edges = edges->next;
    }
    return points;
}

PointList * findPoints(EdgeList * edges, int dir, double (*getXY)(Point *p)){
    Edge * list = edges->edges;

    if(list != NULL){
        PointList * points = newPointList(edges->length);
        if(dir*getXY(list->a) > dir*getXY(list->b))
            addPoint(points, list->a);
        else if(getXY(list->a) == getXY(list->b)){
            addPoint(points, list->a);
            addPoint(points, list->b);
        }
        else
            addPoint(points, list->b);
        while(list->next != NULL){
            if(dir*getXY(list->next->a) > dir*getXY(points->points[0])){
                freePointList(points);
                points = newPointList(edges->length);
                addPoint(points, list->next->a);
                if(getXY(list->next->a) == getXY(list->next->b))
                    addPoint(points, list->next->b);
            }
            if(dir*getXY(list->next->b)> dir*getXY(points->points[0])){
                freePointList(points);
                points = newPointList(edges->length);
                addPoint(points, list->next->b);
            }
            else if(getXY(list->next->a) == getXY(points->points[0])){
                addPoint(points, list->next->a);
                if(getXY(list->next->a) == getXY(list->next->b))
                    addPoint(points, list->next->b);
            }
            list = list->next;
        }
        return points;
    }
    else
        return NULL;
}


PointList * findHighestPoints(EdgeList * edges){
    return findPoints(edges,1,getPointY);
}
PointList * findLowestPoints(EdgeList * edges){
    return findPoints(edges,-1,getPointY);
}
PointList * findRightBoundaryPoints(EdgeList * edges){
    return findPoints(edges,1,getPointX);
}
PointList * findLeftBoundaryPoints(EdgeList * edges){
    return findPoints(edges,-1,getPointX);
}

int checkMaxYCloudPos(EdgeList * left, EdgeList * right){
    PointList * left_highest = findHighestPoints(left);
    PointList * right_highest = findHighestPoints(right);

    if(left_highest->points[0]->y >= right_highest->points[0]->y)
        return 0;
    else
        return 1;
}

int checkMinYCloudPos(EdgeList * left, EdgeList * right){
    PointList * left_lowest = findLowestPoints(left);
    PointList * right_lowest = findLowestPoints(right);

    if(left_lowest->points[0]->y <= right_lowest->points[0]->y)
        return 0;
    else
        return 1;
}

Point * getOnePoint(PointList * points, int dir, double (*getXY)(Point *p)){
    Point * p = points->points[0];
    int i;
    for(i=1; i<points->length; i++){
        if(dir*getXY(p) < dir*getXY(points->points[i])){
            p = points->points[i];
        }
    }
    return p;
}


Point * findMaxLeftUpPoint(EdgeList * edges){
    PointList * points = findLeftBoundaryPoints(edges);
    return getOnePoint(points, 1, getPointY);
}

Point * findMaxLeftDownPoint(EdgeList * edges){
    PointList * points = findLeftBoundaryPoints(edges);
    return getOnePoint(points, -1, getPointY);
}

Point * findMaxRightUpPoint(EdgeList * edges){
    PointList * points = findRightBoundaryPoints(edges);
    return getOnePoint(points, 1, getPointY);
}

Point * findMaxRightDownPoint(EdgeList * edges){
    PointList * points = findRightBoundaryPoints(edges);
    return getOnePoint(points, -1, getPointY);
}

Point * findMaxUpLeftPoint(EdgeList * edges){
    PointList * points = findHighestPoints(edges);
    return getOnePoint(points, -1, getPointX);
}

Point * findMaxUpRightPoint(EdgeList * edges){
    PointList * points = findHighestPoints(edges);
    return getOnePoint(points, 1, getPointX);
}

Point * findMaxDownLeftPoint(EdgeList * edges){
    PointList * points = findLowestPoints(edges);
    return getOnePoint(points, -1, getPointX);
}

Point * findMaxDownRightPoint(EdgeList * edges){
    PointList * points = findLowestPoints(edges);
    return getOnePoint(points, 1, getPointX);
}

Point * getClockDirPoint(Edge * list, Point * p, Point * other, Point * stop, int dirX){
    Point * w = NULL;
    int side;
    while(list != NULL){
        if(compare(list->a, p) == 0 && (other == NULL || compare(list->b, other) != 0)){
            if((side = halfPlane(list->b, stop, p)*dirX) <= 0){
                if(side < 0)
                    return list->b;
                else
                    w = list->b;
            }
        }
        else if(compare(list->b, p) == 0 &&(other == NULL || compare(list->a, other) != 0)){
            if((side = halfPlane(list->a, stop, p)*dirX) <= 0){
                if(side < 0)
                    return list->a;
                else
                    w = list->a;
            }
        }
        list = list->next;
    }
    return w;
}

PointList * getClockDirectionPointsList(EdgeList * edges, Point * start, Point * stop, int dirX, int dirY){
    PointList * points = newPointList(edges->length);
    Point * prev = NULL, * next;
    Edge * list = edges->edges;
    addPoint(points, start);
    next = getClockDirPoint(list, start, prev, stop, dirX);
    while(compare(next,stop) != 0){
        addPoint(points, next);
        prev = start;
        start = next;
        next = getPoint(list, start, prev,dirX, dirY);
        if(next == NULL)
            break;
    }
    addPoint(points, stop);
    return points;
}

PointList * getRightClockPointsList(EdgeList * edges, Point * start, Point * stop){
    return getClockDirectionPointsList(edges,start,stop,1,1);
}

PointList * getLeftClockPointsList(EdgeList * edges, Point * start, Point * stop){
    return getClockDirectionPointsList(edges,start,stop,-1,1);
}


Point * getFirstNextPoint(Edge * list, Point * p, Point * other, int dirX, int dirY){
    Point * w = NULL;
    while(list != NULL){
        if(compare(list->a, p) == 0 && (other == NULL || compare(list->b, other) != 0)){
            if(w != NULL){
                if(dirX*list->b->x >= dirX*p->x && (dirX*w->x < dirX*p->x || (dirY*list->b->y >= dirY*w->y))){//(dirX*w->x >= dirX*p->x && dirY*list->b->y >= dirY*w->y))){
                    return list->b;
                }
                return w;
            }
            else if(w == NULL)
                w = list->b;
        }
        else if(compare(list->b, p) == 0 &&(other == NULL || compare(list->a, other) != 0)){
            if(w != NULL){
                if(dirX*list->a->x >= dirX*p->x && (dirX*w->x < dirX*p->x || (dirY*list->a->y >= dirY*w->y))){//(dirX*w->x >= dirX*p->x && dirY*list->a->y >= dirY*w->y))){
                    return list->a;
                }
                return w;
            }
            else if(w == NULL)
                w = list->a;
        }
        list = list->next;
    }
    return NULL;
}

Point * getPoint(Edge * list, Point * p, Point * other, int dirX, int dirY){
    while(list != NULL){
        if(compare(list->a, p) == 0 && (other == NULL || compare(list->b, other) != 0)){
            return list->b;
        }
        else if(compare(list->b, p) == 0 &&(other == NULL || compare(list->a, other) != 0)){
            return list->a;
        }
        list = list->next;
    }
    return NULL;

}

PointList * getSpecDirectionPointsList(EdgeList * edges, Point * start, Point * stop, int dirX, int dirY){
    PointList * points = newPointList(edges->length);
    Point * prev = NULL, * next;
    Edge * list = edges->edges;
    addPoint(points, start);
    next = getFirstNextPoint(list, start, prev, dirX, dirY);
    while(compare(next,stop) != 0){
        addPoint(points, next);
        prev = start;
        start = next;
        next = getPoint(list, start, prev,dirX, dirY);
        if(next == NULL)
            break;
    }
    addPoint(points, stop);
    return points;
}

PointList * getRightUpDirectionPointsList(EdgeList * edges, Point * start, Point * stop){
    return getSpecDirectionPointsList(edges,start,stop,1,1);
}

PointList * getLeftUpDirectionPointsList(EdgeList * edges, Point * start, Point * stop){
    return getSpecDirectionPointsList(edges,start,stop,-1,1);
}

PointList * getRightDownDirectionPointsList(EdgeList * edges, Point * start, Point * stop){
    return getSpecDirectionPointsList(edges,start,stop,1,-1);
}

PointList * getLeftDownDirectionPointsList(EdgeList * edges, Point * start, Point * stop){
    return getSpecDirectionPointsList(edges,start,stop,-1,-1);
}

Edge * checkSequences(PointList * left, PointList * right, EdgeList * all_left, EdgeList * all_right, int shift, int dir, Edge * prev){
    int i;
    Edge * tmp = prev;
    for(i=shift; i<left->length; i++){
        if(isPointVisibleFromPlaceByEdges(left->points[i], right->points[shift], all_left, all_right)){
            Edge * e = newEdge();
            e->a = left->points[i];
            e->b = right->points[shift];
            if(tmp == NULL)
                tmp = e;
            else if(!isIntersect(e,tmp) && !isIntersect(tmp,e) && dir*halfPlane(e->a, tmp->a, tmp->b) >= 0 && dir*halfPlane(e->b, tmp->a, tmp->b) >= 0)
                tmp = e;
        }
    }
    for(i=1+shift; i<right->length; i++){
        if(isPointVisibleFromPlaceByEdges(left->points[shift], right->points[i], all_left, all_right)){
            Edge * e = newEdge();
            e->a = left->points[shift];
            e->b = right->points[i];
            if(tmp == NULL)
                tmp = e;
            else if(!isIntersect(e,tmp) && !isIntersect(tmp,e) && dir*halfPlane(e->a, tmp->a, tmp->b) >= 0 && dir*halfPlane(e->b, tmp->a, tmp->b) >= 0)
                tmp = e;
        }
    }
    return tmp;
}

Edge * findConnectionEdge(PointList * left, PointList * right, EdgeList * all_left, EdgeList * all_right, int dir){
    int i, n = left->length;
    Edge * e = NULL;
    Edge * edge = NULL;
    if(left->length >= right->length)
        n = right->length;
    for(i = 0; i < n; i++){
        e = checkSequences(left,right,all_left, all_right, i, dir, edge);
        if(e != NULL)
            edge = e;
    }
    return edge;
}

int isPointVisibleFromPlaceByEdges(Point * point, Point * place, EdgeList * all_left, EdgeList * all_right){
    int i=0;
	Edge * e1 = newEdge();
	Edge * e2 = all_left->edges;
	e1->a = point;
	e1->b = place;

    for(i=0; i<all_left->length; i++){
        if(compare(e1->a, e2->a) != 0 && compare(e1->a, e2->b) != 0 &&
           compare(e1->b, e2->a) != 0 && compare(e1->b, e2->b) != 0 &&
           (isIntersect(e1, e2) && isIntersect(e2, e1)) &&
           !isCoplanarWithPoints(e1->a, e2->a, e2->b) && !isCoplanarWithPoints(e1->b, e2->a, e2->b)){
            return 0;
        }
        e2 = e2->next;
    }
    e2 = all_right->edges;
    for(i=0; i<all_right->length; i++){
        if(compare(e1->a, e2->a) != 0 && compare(e1->a, e2->b) != 0 &&
           compare(e1->b, e2->a) != 0 && compare(e1->b, e2->b) != 0 &&
           isIntersect(e1, e2) && isIntersect(e2, e1) &&
           !isCoplanarWithPoints(e1->a, e2->a, e2->b) && !isCoplanarWithPoints(e1->b, e2->a, e2->b)){
            return 0;
        }
        e2 = e2->next;
    }
    return 1;
}

int isPointVisibleFromPlaceByPoints(Point * point, Point * place, PointList * all_left, PointList * all_right){
    int i=0;
	Edge * e1 = newEdge();
	Edge * e2 = newEdge();
	e1->a = point;
	e1->b = place;

    for(i=0; i<all_left->length-1; i++){
		e2->a = all_left->points[i];
		e2->b = all_left->points[i+1];
        if(compare(e1->a, e2->a) != 0 && compare(e1->a, e2->b) != 0 &&
           compare(e1->b, e2->a) != 0 && compare(e1->b, e2->b) != 0 &&
           isIntersect(e1, e2) && isIntersect(e2, e1) &&
           !isCoplanarWithPoints(e1->a, e2->a, e2->b) && !isCoplanarWithPoints(e1->b, e2->a, e2->b)){
            return 0;
        }
    }
    for(i=0; i<all_right->length-1; i++){
        e2->a = all_right->points[i];
		e2->b = all_right->points[i+1];
        if(compare(e1->a, e2->a) != 0 && compare(e1->a, e2->b) != 0 &&
           compare(e1->b, e2->a) != 0 && compare(e1->b, e2->b) != 0 &&
           isIntersect(e1, e2) && isIntersect(e2, e1) &&
           !isCoplanarWithPoints(e1->a, e2->a, e2->b) && !isCoplanarWithPoints(e1->b, e2->a, e2->b)){
            return 0;
        }
    }
    return 1;
}

TriangleList * makeTriangles(PointList * bigger_list, PointList * smaller_list){
    TriangleList * triangles = newTriangleList(bigger_list->length+smaller_list->length);
    int i = 0, j = 0, k = 0, l = 0;
    int m = smaller_list->length;
    int n = bigger_list->length;
    int change1, change2;
    int visible1, visible2;

    while(i < m-1 || j < n-1){
        change1 = 0;
        while(i < m && j < n-1 &&
              (((visible1 = isPointVisibleFromPlaceByPoints(smaller_list->points[k], bigger_list->points[l], smaller_list, bigger_list)) == 1 &&
                (visible2 = isPointVisibleFromPlaceByPoints(smaller_list->points[k], bigger_list->points[j+1], smaller_list, bigger_list)) == 1 ))){
            Triangle * tl = newTriangle();
            tl->a = smaller_list->points[k];
            tl->b = bigger_list->points[l];
            tl->c = bigger_list->points[j+1];
            addTriangle(triangles, tl);
            change1 = 1;
            j++;
            l = j;
        }
        if(isPointVisibleFromPlaceByPoints(smaller_list->points[k], bigger_list->points[j], smaller_list, bigger_list) == 0 && !visible2){
            Triangle * tl = newTriangle();
            tl->a = bigger_list->points[l];
            tl->b = bigger_list->points[j];
            tl->c = bigger_list->points[j+1];
            addTriangle(triangles, tl);
        }
        if(!change1 && !change2){
            i++;
            change1 = 1;
        }

        change2 = 0;
        while(j < n && i < m-1 &&
              (((visible1 = isPointVisibleFromPlaceByPoints(smaller_list->points[k], bigger_list->points[l], smaller_list, bigger_list)) == 1 &&
                (visible2 = isPointVisibleFromPlaceByPoints(smaller_list->points[i+1], bigger_list->points[l], smaller_list, bigger_list)) == 1 ))){
            Triangle * tl = newTriangle();
            tl->a = bigger_list->points[l];
            tl->b = smaller_list->points[k];
            tl->c = smaller_list->points[i+1];
            addTriangle(triangles, tl);
            change2 = 1;
            i++;
            k = i;
        }
        if(isPointVisibleFromPlaceByPoints(smaller_list->points[i], bigger_list->points[l], smaller_list, bigger_list) == 0 && !visible2){
            Triangle * tl = newTriangle();
            tl->a = smaller_list->points[l];
            tl->b = smaller_list->points[i];
            tl->c = smaller_list->points[i+1];
            addTriangle(triangles, tl);
        }
        if(!change1 && !change2){
            j++;
            change2 = 1;
        }
    }
    return triangles;
}

TriangleList * makeConnectionTriangles(PointList * left_visible_points, PointList * right_visible_points){
    if(left_visible_points->length >= right_visible_points->length){
        return makeTriangles(left_visible_points, right_visible_points);
    }
    else{
        return makeTriangles(right_visible_points, left_visible_points);
    }
}

EdgeList * makeNewConvexHull(PointList * left_visible_points, EdgeList * left,
                             PointList * right_visible_points, EdgeList * right,
                             Edge * top_edge, Edge * bottom_edge){
    int i;
    Edge * current_edge = newEdge();
    for(i=0; i < left_visible_points->length-1; i++){
        current_edge->a = left_visible_points->points[i];
        current_edge->b = left_visible_points->points[i+1];
        deleteEdge(left, current_edge);
    }

    for(i=0; i < right_visible_points->length-1; i++){
        current_edge->a = right_visible_points->points[i];
        current_edge->b = right_visible_points->points[i+1];
        deleteEdge(right, current_edge);
    }
    addAllEdges(left,right);
    addEdge(left,top_edge);
    addEdge(left,bottom_edge);
    freeEdge(current_edge);
    return left;
}


TriangleList * mergeTwoTriangulations(EdgeList * left, EdgeList * right){
    Point * left_start;
    Point * left_stop;
    Point * right_start;
    Point * right_stop;

	PointList * left_selected_points;
    PointList * right_selected_points;

	PointList * left_visible_points;
    PointList * right_visible_points;

	Edge * top_edge, * bottom_edge;

	int cloud_max;

    /*Checking which point cloud have the highest point and based on this
    - selecting specyfic groups of boundary points in both clouds*/
    if(!(cloud_max = checkMaxYCloudPos(left,right))){
        left_start = findMaxUpLeftPoint(left);
        left_stop = findMaxRightDownPoint(left);
        right_start = findMaxRightDownPoint(right);
        right_stop = findMaxUpLeftPoint(right);
    }
    else{
        left_start = findMaxLeftDownPoint(left);
        left_stop = findMaxUpRightPoint(left);
        right_start = findMaxUpRightPoint(right);
        right_stop = findMaxLeftDownPoint(right);
    }

    /*Creating point queues with specified directions from selected points*/
    left_selected_points = getRightUpDirectionPointsList(left, left_start, left_stop);
    right_selected_points = getLeftUpDirectionPointsList(right, right_start, right_stop);

    /*Creating top edge based on created queues*/
    top_edge = findConnectionEdge(left_selected_points, right_selected_points, left, right,1);

    /*Checking which point cloud have the lowest point and based on this
    - selecting specyfic groups of boundary points in both clouds*/
    if(!checkMinYCloudPos(left,right)){
        left_start = findMaxDownLeftPoint(left);
        left_stop = findMaxRightUpPoint(left);
        right_start = findMaxRightUpPoint(right);
        right_stop = findMaxDownLeftPoint(right);
    }
    else{
        left_start = findMaxLeftUpPoint(left);
        left_stop = findMaxDownRightPoint(left);
        right_start = findMaxDownRightPoint(right);
        right_stop = findMaxLeftUpPoint(right);
    }

    /*Creating point queues with specified directions from selected points*/
    right_selected_points = getLeftDownDirectionPointsList(right, right_start, right_stop);
    left_selected_points = getRightDownDirectionPointsList(left, left_start, left_stop);

    /*Creating top edge based on created queues*/
    bottom_edge = findConnectionEdge(left_selected_points, right_selected_points, left, right,-1);

    /*Selecting visible points from first cloud to second, and vice versa*/
    left_visible_points = getRightClockPointsList(left, top_edge->a, bottom_edge->a);
    right_visible_points = getLeftClockPointsList(right, top_edge->b, bottom_edge->b);

    /*Making new convex hull based on all points except for visible points*/
    left = makeNewConvexHull(left_visible_points, left, right_visible_points, right, top_edge, bottom_edge);

    /*Making triangles which will connect two point clouds*/
    return makeConnectionTriangles(left_visible_points, right_visible_points);
}

TriangleList * mergeAllTriangulations(EdgeList ** edge_list, int n){
    int i;
    int size = 0;
	TriangleList * all_triangles;
	EdgeList * left_list;
    for(i = 0; i < n; i++){
        size += edge_list[i]->length;
    }
    all_triangles = newTriangleList(size);
    left_list = edge_list[0];
    for(i = 1; i < n; i++){
        addAllTriangles(all_triangles, mergeTwoTriangulations(left_list, edge_list[i]));
    }
    return all_triangles;
}

